/*************************************************************************
 * File Name:    Valid_Parentheses.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/13 22:34:36
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Valid Parentheses
 |
 | Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
 | determine if the input string is valid.
 |
 | The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
private:
    bool valid_bracket(char a, char b)
    {
        if (a == '(') return b == ')';
        if (a == '[') return b == ']';
        if (a == '{') return b == '}';
        return false;
    }
    
public:
    bool isValid(string s)
    {
        stack<char> sta;
        
        for (size_t i = 0; i < s.size(); ++i) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                sta.push(s[i]);
            } else {
                if (sta.empty() || !valid_bracket(sta.top(), s[i])) return false;
                sta.pop();
            }
        }
        return sta.empty();
    }
};

